1. Field of the Invention
This invention relates to a method and apparatus for mapping digital data to symbols in a symbol constellation with such symbols representing in the modulation of a carrier signal for transmission over a transmission medium.
2. Description of Prior Art
In data communications equipment (DCE), such as modems, the digital data from data terminal, equipment (DTE) is inputted using the bit rate clock and mapped onto one of the members of an alphabet, such alphabet comprising one of M symbols (i.e., points) of a signal constellation. This mapping occurs at the symbol rate, and thereafter during each symbol interval, i.e., baud, the symbol is transmitted over a transmission medium. At a receiver in another DCE, the constellation symbol is recovered and the bit sequence representing the symbol is sent to another DTE.
The non-coded system of FIG. 1, is the simplest case of the above described DCE. K bits from the DTE are mapped on to 2.sup.k =M symbols of a two dimensional symbol constellation by a symbol mapper 2 in the transmitter and transmitted over a baseband channel 4 to a receiver 6, wherein a slicer and decoder retrieves the K bits. This is a binary mapped system in that the number of symbols in the constellation, M, is a function of the base or radix 2 raised to the power of the whole number K, with K being the number of bits coded at a time during each baud. In other words, when using binary mapping to transmit K bits per baud, a symbol constellation of 2.sup.k symbols is required and each of the K bit sequences is represented by one of the members (symbols) of this constellation, such constellation being a limited subset of all possible constellations. For example, with binary mapping, the number of points of a constellation, M, is always an even number and therefore all constellations having an odd number of symbols are excluded. As will be seen hereinafter, all the prior art schemes, in determining the number of symbols in a constellation, use this binary mapping concept.
As shown in FIG. 2, even in the more complicated multidimensional coding schemes, the same binary mapping process as described for the uncoded system is incorporated. Generally in these convolutionally encoded systems, some of the data bits from DTE are expanded by the convolutional encoder 8 and thereafter these coded bits select the sub-constellation (i.e., subset) to which the transmit symbol belongs. The rest of the data bits from blocks 10 and 12 are uncoded and are used to pick a symbol of the sub-constellation in the same way as mentioned above in the uncoded system. More specifically, one illustrative embodiment of a multidimensional coding scheme fitting the diagram of FIG. 2 is a 19.2K bps, eight dimensional, convolutionally encoded modem described in U.S. Pat. No. 4,761,784 which is incorporated by reference. In this modem, there is a group time interval extending over four bauds and includes a frame of 28 data bits. These 28 bits per frame, after being expanded to 29 bits, are allocated over the four bauds to create fractional bits per baud as follows ("x" indicates bits):
______________________________________ Uncoded Bits Coded Bits ______________________________________ 21 bits(5.25 bits/baud) 7 bits(1.75 bits/baud) uncoded bit to constellation symbol index coder (+1) (5.25 bits/baud) (2 bits/baud) 1 2 3 4 1 2 3 4 ______________________________________ 0 xxxxx xxxxx xxxxx xxxxx xx xx xx xx 1 00 xxx xxxxx xxxxx xxxxx xx xx xx xx 1 01 xxxxx xxx xxxxx xxxxx xx xx xx xx 1 10 xxxxx xxxxx xxx xxxxx xx xx xx xx 1 11 xxxxx xxxxx xxxxx xxx xx xx xx xx ______________________________________
As described in more detail in the above referenced patent, each baud two coded bits from the convolutional encoder 8 ("coder") and either five or three uncoded bits from an index generator 10 are selected to look up the transmit symbol in a look-up table. Together these coded and uncoded bits access the 160 symbol (2.sup.7 +2.sup.5) constellation, which is subdivided into sub-constellations, i.e, subsets. Each sub-constellation contains 40 symbols (2.sup.5 inner symbols+2.sup.3 outer symbols). More specifically, 21 bits of each four baud frame of 28 bits are uncoded. By way of the fraction mapper 12, one uncoded bit specifies whether there is an outer symbol (otherwise, as shown in row 1, these are all inner symbols) as indicated in column 1 in the above chart. If there is an outer symbol, column 2 indicates in which of the four bauds it occurs. The next four columns (specified by the bauds 1 through 4 in the chart) show the remaining uncoded bits (three bits or five bits) spread over the four bauds, with five uncoded bits being required to specify an inner symbol and three uncoded bits required to specify an outer symbol. Since this implementation requires fractional uncoded bits per baud (5.25 bits per baud), the above described technique of switching between inner and outer symbols allows for a whole number of uncoded bits per baud to specify a given symbol in either the inner or outer signal constellation. However, both the inner and outer signal constellations use binary mapping, i.e., the number of points is a function of radix 2 raised by some whole number power, e.g., to the power of five or three depending upon whether it is an inner or outer point, respectively. In FIG. 2, the diagram is also shown to be generic to those systems that also have "middle points". Symbol mappers 14 and 16 are shown merely to illustrate the fact that there is a new symbol mapper for each of the four baud intervals in the illustrative eight dimensional convolutionally encoded system. This kind of known binary mapping, as presented in this example, will be referred to as "fractional bit binary mapping.
An alternative type of well known binary mapping that could have been used in the above 19.2K modem example will be referred to as "whole bit binary mapping". With this scheme, any fraction is expressed by the existence or absence of whole bits. For example, a 1/4 fraction is equivalent to 1, 0, 0, 0, where out of every fourth frame one frame uses one more bit per baud (thereby doubling the constellation) over the other three frames. In the above 19.2k example, seven bits can be transferred in each of three bauds and eight bits could be transferred in one baud.
As a further example of the exclusive use of binary mapping in a two dimensional convolutionally encoded system, the CCITT V.32 Standard specifies the transmission of an integer number of bits per baud, i.e., 5 bits per baud, with four data bits per baud being expanded by two dimensional convolutional encoding to the 5 bits per baud as shown in the following chart ("X" indicates bits):
______________________________________ Uncoded Bits Coded Bits ______________________________________ 2 bits/baud 2 bits/baud uncoded bit to constellation symbol index coder (+1 bit) 2 bits/baud) (3 bits/baud) xx xxx ______________________________________
In this modem during each baud, three coded bits from the convolution encoded ("coder") and two uncoded bits are used to access a 2.sup.5 =32 symbols constellation for generating transmit symbol Note that unlike the previous eight dimensional, 19.2K bps example, there are no fractional bits per baud, but again, binary mapping is used, i.e., 2.sup.5 symbols exist in the constellation.
The use of an 8-dimensional or 4-dimensional convolutionally encoded system instead of a 2-dimensional convolutionally encoded system allows for a reduction in the number of additional symbols required for the redundancy coding; however, in all three cases binary mapping is used.
In FIG. 3 a block coder system is shown having a block coder 18, with n bits being allocated between the uncoded bits 20 and the fractional mapper 22 and, with there being a different symbol mapper (illustrated by mappers 24 and 26) for each baud of the group interval over which mapping occurs. Again, as can been seen, binary mapping is used.
Four illustrative examples of various uncoded and coded systems were shown above to illustrate the use of binary mapping in prior art schemes. However, binary mapping has a number of deficiencies as will be described below. First, there is a loss in bit mapping efficiency for systems utilizing fractional bit rates, such as illustrated by the 19.2K system of FIG. 2, as compared whole integer bit rate systems, such as the CCITT V.32 system described above. In the CCITT V.32 system all 32 symbols are equi-probable and a 32 symbol set can represent only 5 bits. So, it is 100% efficient. In the 19.2K system, the 160 symbols are not equi-probable, so part of the fractional bits are lost. A 160 symbol constellation can represent 7.322 bits per baud, yet in 19.2K system described above, due to the binary mapping, it is used to represent only 7.25 bits per baud. This is only 99% efficient. A binary mapped six symbol constellation is only 96.5% efficient, etc.
Secondly, as previously explained, a binary mapped system does not have the ability to generate a map for any constellation. Obviously, any constellation containing odd number of symbols cannot be represented by a binary mapping technique. This limits the data rate adaptability to the channel and a DCE's capacity to provide incremental data rates to the customer. For example, the binary mapping cannot represent a three symbol constellation, so the data rate of such a system has to be brought down to map into a two symbol constellation, which is only 63% efficient.
Thirdly, as already explained, one problem with the fractional bit binary mapping used in the above described 19.2k system is that, due to the inner and outer symbol constellations, the symbols are not equally probable, i.e., the system is not deterministic. Hence, problems are created when Tomlinson precoding is incorporated into such a system.